For the benefit of the reader, a numbered list of several related references is included below. Several of these references are referred to below using one or more bracketed numbers. For example, listing [8] at the end of a particular sentence indicates that Reference 8, below, may be of relevance, for background purposes, to that particular sentence.    [1] K. J. Arrow: “Social Choices and Individual Values,” Wiley and Sons, New York, 1963    [2] E. H. Clarke: “Multipart pricing of public goods,” Public Choice 11, pp. 17-33, 1971    [3] R. Dechter: “Constraint Processing,” Morgan-Kaufmann Publishers, 2003    [4] E. Ephrati and J. S. Rosenschein: “The Clarke tax as a consensus mechanism among automated agents,” Proceedings of the 9th National Conference on Artificial Intelligence, pp. 173-178, San Jose, Calif., July 1991.    [5] J. Green, J. J. Laffont: “Incentives in public decision making,” Studies in Public Economics 1, North-Holland, 1979    [6] T. Groves: “Incentives in Teams,” Econometrica 41, pp. 617-663, 1973    [7] H. Moulin: “Axioms of Cooperative Decision-making,” Econometric Society Monographs 15, Cambridge University Press, 1988    [8] R. B. Myerson, M. A. Satterthwaite: “Efficient Mechanisms for Bilateral Trading,” Journal of Economic Theory 29, pp. 265-281, 1983    [9] N. Nisan and A. Ronen: “Computationally feasible VCG Mechanisms,” Proceedings of the 2nd ACM Conference on Electronic Commerce, 2000    [10] W. Vickrey: “Counterspeculation, Auctions, and Competitive Sealed Tenders,” Journal of Finance 16, pp. 8-37, 1961.
Many practical situations involve a social choice problem in which a group of agents has to choose an outcome that best fits their combined preferences. For example, a group going out to have dinner together has to choose a restaurant that fits everyone's preferences. Tenants of a building have to decide on features of a planned renovation. Spectrum has to be divided up among different mobile telephone providers.
A mechanism for solving a social choice problem is a method algorithm that takes as inputs declarations of the agents' utilities for each outcome, and outputs as a solution the optimal choice plus possibly other information.
Social choice problems become difficult to solve when agents have conflicting preferences, as each agent will exaggerate its preferences to obtain a better outcome for itself.
It is possible to counteract this tendency using tax schemes where agents have to pay for the preferences they claim. An example of such tax schemes are auctions: the social choice is to decide who receives the good being auctioned, and the winner has to make a payment that depends on how strongly he claims to value the good.
In an incentive-compatible (IC) mechanism, the incentives of each agent are aligned with those of the group: the behavior that optimizes the utility of an individual agent also optimizes the utility of the group. When utility optimization is left to the social choice mechanism, this often corresponds to each agent being best off declaring its preferences truthfully; this is called truthful or strategyproof Such a mechanism makes life easy for the agents since they do not have to speculate to obtain the best outcome. It also avoids choosing a suboptimal outcome because of such speculation.
A well-known mechanism for achieving IC is the Vickrey-Clarke-Groves (VCG) tax ([2]) mechanism. It assumes that the mechanism chooses an outcome that maximizes the sum of agents' utilities (called the Pareto-efficient outcome, PE), and makes each agent pay a tax that is calculated so that the agent cannot gain from misreporting its utility. Furthermore, the VCG tax is individually rational (IR) in that the tax paid by an agent never exceeds the utility gain the agent gets from participating in the optimization as opposed to letting the other agents pick the outcome.
Any tax mechanism produces a surplus of taxes that cannot be redistributed to the agents without loosing the incentive-compatible property, i.e. the tax mechanisms are not budget-balanced (BB). In game theory, it has been shown that all incentive-compatible mechanisms that apply to general problems and always generate a Pareto-efficient outcome must use a tax of a form similar to the VCG tax ([5, 7]). It has further been shown that such a mechanism cannot be budget-balanced ([5, 8]).
In the special case of auctions, the surplus can be used to pay the sellers of the goods; the resulting VCG scheme is called the Vickrey auction protocol. However, in many cases, there is no use for this surplus. It reduces agents' utilities, and creates incentives for the receiver of the surplus to manipulate the setting to maximize taxes. For example, in spectrum allocation, governments can obtain huge windfall profits by creating scarcity, but in so doing hurt the public in general.
Accordingly, there is a need for systems and methods that allow social choice to take place without creating any surplus or deficit while still making it in each agent's best interest to follow the solution provided.